package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:DNA序列由一系列核苷酸组成，缩写为'A','C','G'和'T'.。
 *
 * 例如，"ACGAATTCCG"是一个 DNA序列 。
 * 在研究 DNA 时，识别 DNA 中的重复序列非常有用。
 *
 * 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的长度为10的序列(子字符串)。你可以按 任意顺序 返回答案
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/repeated-dna-sequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-19
 * Time:22:37
 */
public class Set187 {
    static final int L = 10;
    Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
        put('A', 0);
        put('C', 1);
        put('G', 2);
        put('T', 3);
    }};

    public List<String> findRepeatedDnaSequences(String s) {//滑动窗口 + 位运算
        List<String> ans = new ArrayList<String>();
        int n = s.length();
        if (n <= L) {
            return ans;
        }
        int x = 0;
        for (int i = 0; i < L - 1; ++i) {
            x = (x << 2) | bin.get(s.charAt(i));
        }
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int i = 0; i <= n - L; ++i) {
            x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            if (cnt.get(x) == 2) {
                ans.add(s.substring(i, i + L));
            }
        }
        return ans;
    }


    public List<String> findRepeatedDnaSequences2(String s) {
        List<String> ans = new ArrayList<String>();//使用map
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }

    public List<String> findRepeatedDnaSequences1(String s) {
        List<String> list = new ArrayList<>();
        if(s == null)return list;
        Set<String> set = new HashSet<>();//存放所有长度为10的字符串
        Set<String> a = new HashSet<>();//去重
        for(int i = 0;i < s.length();i ++){
            if(i + 10 <= s.length()){
                if(!set.contains(s.substring(i,i + 10))){
                    set.add(s.substring(i,i + 10));
                }else{
                    a.add(s.substring(i,i + 10));
                }
            }else{
                break;
            }
        }
        for(String w : a){
            list.add(w);
        }
        return list;
    }
}
